#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/9/19 15:42
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-合并区间.py
# @Software: PyCharm

# Definition for an interval.


class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

    def __str__(self):
        return '[%d, %d]' % (self.start, self.end)


class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        def getStart(inter):
            return inter.start
        intervals.sort(key=getStart)
        ans = []
        for i in range(len(intervals)):
            an = len(ans)
            x = intervals[i]
            if an <= 0:
                ans.append(x)
            else:
                y = ans[an-1]
                if x.start <= y.end < x.end:
                    y.end = x.end
                elif y.end < x.start:
                    ans.append(x)
        return ans


def makeIntervals(arr):
    ret = []
    for x in arr:
        ret.append(Interval(x[0], x[1]))
    return ret


def printIntervals(arr):
    for i in range(len(arr)):
        print(arr[i], end=(',' if i < len(arr)-1 else '\n'))


def main():
    solve = Solution()
    intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    intervals = [[1, 3], [2, 6], [18, 10], [15, 18]]
    printIntervals(intervals)
    ans = solve.merge(makeIntervals(intervals))
    printIntervals(ans)


if __name__ == '__main__':
    main()
